This invention relates to the mathematical analysis and manipulation of ordered information, such as color, specifically for the mapping of complex color effects onto images encoded using fractal geometry and computer graphic image technology.
This invention derives elements from the fields of color science, fractal geometry and information visualization in computer graphics. Various systems have been used to represent colors. Computers usually represent color by the amount of red, green and blue components, and printing uses the four component cyan, yellow, magenta and black. Human color vision is based on a system of primary receptors for red, yellow and blue.
The first standardization of the specification and quantitative classification of color and the differences between color occurred in 1931. The Commission Internationale d'Elairage (CIE-The International Commission on Illumination) picked the lighting standards under which color would be measured and classified. A filter was used which produced a spectrum very close to daylight when illuminated with a tungsten lamp at the proper temperature, this became known as Illuminant Standard C. A second standard called Illuminant Standard A was adopted which has a similar energy distribution to a gas-filled tungsten lamp.
The measurement of color was standardized using a tri-stimulus system. X represents the spectral color red at 600 nm, and X represents a standard more saturated than X. Y and Y represent a more saturated standard and spectral green respectively at 520 nm, and Z and Z represent a more saturated standard and spectral blue at 477 nm. Any color can be represented thereby by integrating over the region of the spectrum which represent the peaks for the red, green and blue standards. The calculations are lengthy and computerized spectrophotometers and photoelectric cells are commonly used. The color standards were chosen so that the green standard matched exactly the reading for that wavelength on a curve of luminosity/unit of power as a function of wavelength. In this way the luminance of colors can be related to the luminance of pure white or black.
Because color is represented, measured and quantified using color space, graphical methods are useful for visualizing aspects of color space. Because color space is a three-dimensional entity, it is difficult to represent graphically in two dimensions. For this reason, a two-dimensional system was developed called the chromaticity diagram. The red component of a color described using the tri-stimulus system is given by the formula x=X/(X+Y+Z). The green component is y=Y/(X+Y+Z) and blue is z=Z/(X+Y+Z). Because x+y+z=1, only two of these quantities are independent and color can be represented by graphing two of the above quantities. Colors can be plotted on the x-y, x-z and y-z planes. The y-x plane is normally used for the chromaticity diagram.
The chromaticity diagram allows additive color mixture to be accomplished graphically. This cannot be done using the RGB tri-stimulus coordinates of two colors. The chromaticity diagram has a serious limitation for color measurement and the visualization of relationships between colors. A chromaticity diagram is a two-dimensional projection of a three-dimensional space. It contains distortions similar to those seen in the two-dimensional Mercator projection of the earth commonly used in maps. The distances between two colors in the chromaticity diagram do not necessarily accurately reflect their actual positions in color space.
The system just described is mainly used for quantitative color specification. To represent color in a manner which is most useful in the fields of art, design, and color photography requires a system of color ordering. The attempt to order colors has a rich history. It is believed that Leonardo da Vinci was the first to attempt color ordering by painting similar colors close to one another, and different colors further away. Newton was the first to arrange the hues in a circle with complementary hues occupying opposite positions on the circle. In 1745, Moses Harris arranged colors of the same hue but increasing saturation at increasing distances from the center along the radius of a circle.
Ostwald in the early 1900s distributed grays between black and white along an axis perpendicular to the circle of hues. Ostwald used a double cone for color space, a system that did not accurately reflect the quantitative relationships. The Ostwald system was the first to order color as a function of all three descriptive variables. These are most commonly called hue, saturation and value. Hue is the actual color such as red, green or blue. Saturation is the amount of the color. Colors with very low saturation are almost on the grey scale. Value is the same as brightness. Value orders colors with hue along the grey scale from black with O value to white with a maximum value.
The double cone of the Ostwald system is not a true representation of color space. Each hue can vary in both brightness and saturation. The true space of hue, saturation, and value (brightness) is a cylinder. At the same time that Ostwald developed his color ordering system, the artist Munsell prepared a series of cards which represented the saturation and value or brightness of different hues. He developed cards for ten hues, ten value gradations and three to eight saturation steps for each view. These cards have been commercially available since 1904. The Munsell system has been very useful for artists and designers because it provides a logical and correct ordering of colors.
A technical analysis of color shows that hue corresponds to spectral frequency range, brightness corresponds to amplitude (as a function of frequency) and saturation corresponds to signal-to-noise ratio (as a function of frequency).
The Optical Society of America has evaluated the color order systems and used human observers to develop uniform color scales representing the color continuity and metric. A standardized set of scales was adopted in 1974. The optical society decided to adopt a set of 500 colors in Munsell color space that allowed arrangement into the maximum number of scales. A committee was employed to locate 500 points of equal perceptual distance in the three-dimensional color space based on the Munsell system. The lattice of points was arranged and depicted as colored spheres in a regular rhombohedral crystal. Each point in the lattice is equidistant from twelve other points. A three-dimensional model of this space was built using colored balls. This model contains 422 uniform scales of three or more steps.
The beauty of color use in art is based on the use of such color scales where colors are changed in graded steps. The model constructed by the optical society represents the current state of the art in the visualization of color scales. However, most books on color for artists and designers are restricted to a few major color scales. Tint scales add increasing amount of the achromatic color white to pure hues. Shade scales add increasing amount of achromatic black to pure hues. Tone scales add increasing amounts of colors on the grey scale. There are also "uniform chroma" scales which are tint, tone, or shade scales with compensating amounts of pure hue added to keep saturation constant.
The physical representation of color scales by the Optical Society of America is by no means complete. The lack of completeness has been underscored by the development of twenty-four-bit computer graphic systems which have made palettes of 16.8 million colors available for use. This is a much wider range of color choice than has ever been available to an artist. There have been no tools which enable the visual artist to take full advantage of this color capability. Even the best twenty-four-bit computer painting programs lack techniques which allow color use in computer graphics to come close to the remarkable display of colors in nature. This is one of the starting points for the present invention. What is needed is a systematic tool for utilizing the full color possibilities of twenty-four-bit graphics.
This invention also relates to the visualization of information. The process of map making has been expanded to such maps as maps of galaxy distribution, maps of brain activity, maps of genes on the human genome, and satellite maps of the earth and ocean surfaces. In addition, there is increasingly sophisticated medical imaging and visualization in complex data bases. Many maps use Color to reveal pattern. Heretofore, color choice has been arbitrary and without a systematic method of choosing and scaling colors that best highlight the patterns.
The present invention further relates to fractal geometry, a geometry of fractional dimensions which describes objects or sets via the procedures which generate them. It has been called a geometry of nature, since it describes forms which occur naturally, such as trees, rocks, and clouds, as readily as Euclidean geometry describes triangles, squares, and circles. Fractal geometry describes a complex shape through a recursive procedure used to generate it. An initiator is defined which is a starting line segment, or shape. A "generator" is next formulated, a generator being an operation performed on the initiator which changes it into a more complex shape having multiple copies of the initiator. The generator is employed repeatedly in generations inheriting characteristics of prior generations. In a second application of the generator, the generating procedure is performed on each of the initiators in the first generation. This is continued recursively to a limit which produces a shape that is an "attractor" for that operation.
These definitions have been generalized mathematically to describe what are called Iterated Function Systems (IFS). IFS defines a fractal set as the attractor for a group of linear algebraic transformations which include translation, rotation and dilation. These transformations can be extended to include non-linear transformations. Through this method, the information in a complex object can be reduced or compressed to a simple set of descriptions recitable as algebraic equations for the transformations which converge on an invariant set describing the object.
In order to understand the area of contribution of the present invention, it is useful to consider certain subdisciplines of fractal geometry. The first is in the visualization of mathematical landscapes which evolved from a branch of pure mathematics resulting from the study of polynomial equations. A study of the critical points of the quadratic equation when iterated and studied as a dynamic system resulted in the subdiscipline of nonlinear fractal mappings. A map is made which is called a dynamic plane map. Each point is input into the physically and mathematically significant equation known as the quadratic equation: EQU Ax.sup.2 +Bx+C=0,
which is then solved recursively. Any equation of this form can be conjugated by a coordinate shift to a form: EQU (x.sup.2 +c)=0.
This process generates an orbit, which in the case of the quadratic equation either gets larger, smaller or remains bounded, following a complex (seemingly chaotic) but precise deterministic orbit whose period is generally greater than the resolution of the system of examination. Those points which remain bounded during the iterative mapping are the set of periodic repelling points and are called Julia sets. (All other points on the complex plane for this mapping follow simpler orbits to attractors and are called Fatou sets.) Julia sets are extremely intricate in form and are considered beautiful when expressed visually. A simple technique for expressing a Julia set visually is to make a map, wherein each point of the Julia set is coded as black if it gets smaller or follows a complex orbit to a point of filling a boundary defined by the Fatou set, and is coded white if it gets larger. The quadratic equation has a constant C whose value varies over a certain range. The value C determines the shape of a particular Julia set.
Maps can also be made of the parameter plane where each point represents the value of the parameter C. A parameter plane map is made where each point represents the orbit of the critical point for the Julia set with that C value. As with the Julia sets, this map represents the dynamic category for each point, as it does in the dynamic plane maps.
The dynamic and parameter plane maps contain extremely intricate details which can be revealed by use of color. Maps can be rendered in color using what is called the escape time algorithm wherein those points in a map which are in the category of getting larger are considered to be escaping. Each of these points can be color coded as to the time of escape. The maps that result from using this algorithm are equivalent to contour maps, where a color must be associated with each height. Known color mapping techniques rely on arbitrary choices of colors.
These fractal maps are extremely intricate, and it is difficult to arrive at effective mappings of color onto contour. There are no methods for preparing color palettes for mapping onto fractal maps which can produce color effects to match the sophistication of the geometry. A technique for algorithmically ordering color which matches the sophistication of the detail in the fractal maps would be highly useful.
Another subdiscipline of fractal geometry which can benefit from this invention is fractal landscape generation. Fractal geometry describes many processes in nature, one of which is Brownian motion. This can be represented as random changes in direction of segments of a surface and so generate interesting contours. These are being widely used in computer graphics and even in movie scene generation. Color must be mapped onto these mathematical objects. There is no systematic method of getting realistic effects.
Another subdiscipline of fractal geometry of interest is in fractal image encoding. Barnsley (U.S. Pat. No. 4,941,193) describes a method of using fractal geometry to encode complex images as algebraic transformations. This has application in image compression. These methods can also be used to simulate nature and produce representations of interesting variations on nature. Barnsley utilizes a method of representing a fractal which uses probabilistic iterated function systems where each of the transformations making up part of an image is applied with some preselected probability. The image may be described by a combination of an underlying attractor covered with a distribution of arbitrarily fine grains of dust or sand. After the image is recursively generated mathematically, it can be expressed as a rastered image of pixels wherein the amount of sand in each pixel is summed to produce a number. This number is analogous to the escape time in the escape time algorithm in that it must be mapped onto a color. What is needed are systematic methods for controlling color which can match the capabilities for controlling the geometry.
Any one of these subdisciplines yields an ordered two-dimensional fractal set wherein a number or value at any location in two dimensions is assigned to each point in the fractal set representing a position in a higher (third) dimension.
Known methods of applying color to complex images have been found to be unsatisfactory and aesthetically unsatisfying. While fractal mathematics may capture the mathematics of natural form, there has been no way of also applying the mathematics of natural coloration to fit with the mathematics of natural form.